{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.1 The Bellman-Ford algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-1\n",
    "\n",
    "> Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex $z$ as the source. In each pass, relax edges in the same order as in the figure, and show the $d$ and $\\pi$ values after each pass. Now, change the weight of edge $(z,x)$ to 4 and run the algorithm again, using $s$ as the source."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| \\ | $s$ | $t$ | $x$ | $y$ | $z$ |\n",
    "|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "|$d$|2|4|6|9|0|\n",
    "|$\\pi$|$z$|$x$|$y$|$s$|NIL|\n",
    "\n",
    "| \\ | $s$ | $t$ | $x$ | $y$ | $z$ |\n",
    "|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "|$d$|0|0|2|7|-2|\n",
    "|$\\pi$|NIL|$x$|$z$|$s$|$t$|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-2\n",
    "\n",
    "> Prove Corollary 24.3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No path property."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-3\n",
    "\n",
    "> Given a weighted, directed graph $G = (V, E)$ with no negative-weight cycles, let $m$ be the maximum over all vertices $v \\in V$ of the minimum number of edges in a shortest path from the source $s$ to $v$. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple change to the Bellman-Ford algorithm that allows it to terminate in $m + 1$ passes, even if $m$ is not known in advance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stop when no vertex is relaxed in a single loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-4\n",
    "\n",
    "> Modify the Bellman-Ford algorithm so that it sets $v.d$ to $-\\infty$ for all vertices $v$ for which there is a negative-weight cycle on some path from the source to $v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "if v.d > u.d + w(u, v)\n",
    "     v.d = -inf\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-5 $\\star$\n",
    "\n",
    "> Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \\rightarrow \\mathbb{R}$. Give an $O(VE)$-time algorithm to find, for each vertex $v \\in V$, the value $\\delta^*(v)=\\min_{u \\in V} \\{ \\delta(u, v) \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "RELAX(u, v, w)\n",
    "1 if v.d > min(w(u, v), w(u, v) + u.d)\n",
    "2      v.d > min(w(u, v), w(u, v) + u.d)\n",
    "3      v.pi = u.pi\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 24.1-6 $\\star$\n",
    "\n",
    "> Suppose that a weighted, directed graph $G = (V, E)$ has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on exercise 24.1-4, DFS from a vertex $u$ that $u.d = -\\infty$, if the weight sum on the search path is negative and the next vertex is BLACK, then the search path forms a negative-weight cycle."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
